#!/usr/bin/env python
# -*- encoding: utf-8 -*-
'''
@Author  :   JingV
@Version :   1.0
@Contact :   None
@License :   None
@Desc    :   None
'''


class Solution(object):
    def mySqrt(self, x):
        # 二分法
        if x == 1:
            return 1
        low, heigh = 0, x
        while heigh - low > 1:
            temp = (low + heigh) // 2
            tt = temp * temp
            if tt < x:
                low = temp
            elif tt == x:
                return temp
            else:
                heigh = temp
        return low


def main():
    solution = Solution()
    tests = [1, 2, 4, 8, 9, 25, 0, 100]
    for x in tests:
        print(solution.mySqrt(x))


if __name__ == "__main__":
    main()
